package problem236;

import java.util.Stack;

//236.二叉树的最近公共祖先
//https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

//解法二

class Solution2 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root, p, stack1);
        getPath(root, q, stack2);
        while(stack1.size() > stack2.size()) {
            stack1.pop();
        }
        while(stack2.size() > stack1.size()) {
            stack2.pop();
        }
        //两个栈的元素一样多
        while(stack1.peek() != stack2.peek()) {
            stack1.pop();
            stack2.pop();
        }
        return stack1.peek();
    }

    //获取从 root -> node 节点的路径, 保存到栈中
    private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if(root == null || node == null) return false;
        stack.push(root);
        if(root == node) return true;

        boolean ret1 = getPath(root.left, node, stack);
        if(ret1 == true) {
            return true;
        }
        boolean ret2 = getPath(root.right, node, stack);
        if(ret2 == true) {
            return true;
        }
        stack.pop();
        return false;
    }
}

// 思路:
// 类似与寻找两个相交链表的交点
// 将 root->p 的路径保存到stack1中
// 将 root->q 的路径保存到stack2中
// 让元素个数多的栈弹出差值个元素
// 同时出栈, 当节点相同时停止